package main

import (
	"fmt"
)

type ListNode struct {
	Value int
	Next  *ListNode
}

type v struct {
	Value   int // 0
	Version int // 1,2,3
}

func main() {
	a := []int{1, 2, 3, 4, 5}
	// k:=2

	head := &ListNode{}
	p := head
	for i := 0; i < len(a); i++ {
		node := &ListNode{Value: a[i]}
		p.Next = node
		p = node
	}
	k := 6
	head = reverseList(head.Next, k)
	for head != nil {
		fmt.Print(head.Value, " ")
		head = head.Next
	}
}

func reverseList(head *ListNode, k int) *ListNode {
	hair := &ListNode{Next: head}
	lastTail := hair
	for head != nil {
		tail := lastTail
		for i := 0; i < k; i++ {
			tail = tail.Next
			// 提前到空位，不足k个
			if tail == nil {
				return hair.Next
			}
		}
		nextHead := tail.Next
		tail.Next = nil
		head, tail = reverseK(head, tail)
		lastTail.Next = head // 2 1 |4 3| 5 6
		lastTail = tail
		tail.Next = nextHead
		head = nextHead
	}
	return hair.Next
}

func reverseK(head, tail *ListNode) (*ListNode, *ListNode) {
	t := head
	h := &ListNode{}
	p := head
	for p != nil {
		temp := p
		p = p.Next
		temp.Next = h.Next
		h.Next = temp
	}
	return h.Next, t
}
